package _01_排序;
/*
    稳定的排序算法,时间复杂度O(nlogN),空间复杂度O(n/2+logN)
    ◼ 执行流程
    ① 不断地将当前序列平均分割成2个子序列
    ✓ 直到不能再分割（序列中只剩1个元素）
    ② 不断地将2个子序列合并成一个有序序列
    ✓ 直到最终只剩下1个有序序列
 */
@SuppressWarnings("unchecked")
public class MergeSort05<E extends Comparable<E>> extends Sort<E> {
    private E[] leftArray; //拷贝原数组的左半部分数据
    @Override
    protected void sort() {
        this.leftArray = (E[]) new Comparable[array.length>>1];
        sort(0,array.length);
    }

    /**
     * 类似于二叉树的后序遍历
     * 对[begin,end)范围的元素进行归并排序
     * @param begin
     * @param end
     */
    private void sort(int begin,int end){
        if(end - begin < 2) return; //只有一个或者没元素，不需要排序

        int mid = (begin+end)>>1; //计算中间索引

        //范围都是左闭右开
        //先对数组进行分割，直到每一个都只剩下一个元素
        sort(begin,mid);
        sort(mid,end);

        merge(begin,mid,end);
    }

    /**
     * 将[begin,mid)和[mid,end)两个范围内的数组进行有序合并
     * @param begin
     * @param mid
     * @param end
     */
    private void merge(int begin,int mid,int end){
        int li = 0,le = mid - begin; //左半边数组的指针
        int ri = mid,re = end;
        int ai = begin; //当前待归并数组的起始位置

        //拷贝左半边数组的元素
        for(int i=li;i<le;++i){
            //当前数组的起始位置为begin
            leftArray[i] = array[begin+i];
        }

        //只有左边不结束，才能进行比较,左边结束了就不用比较
        while(li<le){
            //右边结束，将左边数组复制到右边即可
            //排序算法的稳定性
            if(ri<re && cmp(array[ri],leftArray[li])<0){ //右边小于左边
                array[ai++] = array[ri++];
            }else{ //左边小于等于右边
                array[ai++] = leftArray[li++];
            }
        }
    }
}
